package study.lanqiao.com;

import java.text.DecimalFormat;
import java.util.*;

public class t2019 {
    public static void main(String[] args) {
        //t1();
        //t2();
        //t3();
        //t4();
        //t5();
        //t6();
        //t7();
        t8();
    }

    /**
     * 质数
     */
    public static void t1(){
        int MAX = 100000;
        boolean[] arr = new boolean[MAX];
        int cnt = 0;
        for (int i = 2; i < MAX; i++) {
            if (!arr[i]){
                cnt++;
                if (cnt == 2019){
                    System.out.println(i);
                    break;
                }
                for (int j = 2; i * j < MAX; j++) {
                    arr[j * i] = true;
                }
            }
        }
    }

    /**
     * 字串数字
     */
    public static void t2(){
        char[] target = "LANQIAO".toCharArray();
        //char[] target = "LQ".toCharArray();
        long base = 1;
        long res = 0;
        for (int i = target.length - 1; i > -1; i--) {
            res += base * (target[i] - 'A' + 1);
            base = base * 26;
            System.out.println("res:" + res);
            System.out.println("base:" + base);
        }
        System.out.println(res);
    }

    /**
     * 立方和
     */
    public static void t3(){
        long res = 0;
        for (int i = 1; i <= 2019; i++) {
            String s = String.valueOf(i);
            if (s.contains("2") || s.contains("0") || s.contains("1") || s.contains("9")){
                res += Math.pow(i,3);
            }
        }
        System.out.println(String.valueOf(res));
    }
    public static boolean isZhiShu(long n){
        for (long i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static long gcd(long n,long m){
        return m == 0 ? n : gcd(m, n % m);
    }

    /**
     * RSA解密
     * 注意：题目中n的范围很大，18位，如果一个一个遍历，肯定会超时，应当选取合适的开始位置，此处选取开始位置q=10017339
     */
    public static void t4(){
        long n = 1001733993063167141L;
        long d = 212353;
        long c = 20190324;
        long p = 0, q = 0;
        for (p = 10017339; p < n; p++) {
            if (n % p != 0) continue;
            q = n / p;
            if (!isZhiShu(p) || !isZhiShu(q)) continue;
            if (gcd(d,(q - 1) * (p - 1)) == 1){
                break;
            }
        }
        System.out.println("q:" + q);
        System.out.println("p:" + p);
        long cur = (p - 1) * (q - 1);
        long e = 0;
        System.out.println("cur:" + cur);
        //System.out.println("e:" + e);
        for (int i = 1; cur < Long.MAX_VALUE;i++, cur = cur * i){
            if ((cur + 1) % d == 0){
                e = (cur + 1) / d;
                break;
            }
        }
        System.out.println("e:" + e);
    }

    public static void t5(){
        int[][] arr = new int[26][26];
        readPath(arr);
        Map<Integer,HashSet<Integer>> path = new HashMap<Integer, HashSet<Integer>>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] != 0){
                    arr[j][i] = arr[i][j];
                    if (!path.containsKey(i)){
                        path.put(i,new HashSet<Integer>());
                    }
                    if (!path.containsKey(j)){
                        path.put(j,new HashSet<Integer>());
                    }
                    path.get(i).add(j);
                    path.get(j).add(i);
                }
            }
        }
        int[] resCost = new int[]{Integer.MAX_VALUE};
        boolean[] vis = new boolean[26];
        dfs(path,arr,'A' - 'A','S' - 'A',0,resCost,vis);
        System.out.println(resCost[0]);
    }
    public static void dfs(Map<Integer, HashSet<Integer>> path,int[][] costArr,int now,int target,int cost,int[] resCost,boolean[] vis){
        if (now == target){
            resCost[0] = Math.min(resCost[0],cost);
            return;
        }
        HashSet<Integer> nexts = path.get(now);
        for (int next : nexts){
            if (!vis[next]){
                vis[next] = true;
                dfs(path,costArr,next,target,cost + costArr[now][next],resCost,vis);
                vis[next] = false;
            }
        }
    }
    public static int charToIndex(char c){
        return c - 'A';
    }
    public static void readPath(int[][] arr){
        arr[charToIndex('A')][charToIndex('E')] = 1;
        arr[charToIndex('A')][charToIndex('D')] = 1;
        arr[charToIndex('A')][charToIndex('C')] = 1;
        arr[charToIndex('A')][charToIndex('B')] = 2;
        arr[charToIndex('E')][charToIndex('I')] = 3;
        arr[charToIndex('E')][charToIndex('H')] = 1;
        arr[charToIndex('E')][charToIndex('D')] = 1;
        arr[charToIndex('D')][charToIndex('I')] = 2;
        arr[charToIndex('D')][charToIndex('H')] = 1;
        arr[charToIndex('D')][charToIndex('G')] = 2;
        arr[charToIndex('D')][charToIndex('C')] = 3;
        arr[charToIndex('C')][charToIndex('G')] = 3;
        arr[charToIndex('C')][charToIndex('F')] = 3;
        arr[charToIndex('B')][charToIndex('G')] = 1;
        arr[charToIndex('B')][charToIndex('J')] = 2;
        arr[charToIndex('I')][charToIndex('M')] = 3;
        arr[charToIndex('I')][charToIndex('G')] = 3;
        arr[charToIndex('I')][charToIndex('H')] = 1;
        arr[charToIndex('H')][charToIndex('L')] = 2;
        arr[charToIndex('G')][charToIndex('K')] = 2;
        arr[charToIndex('G')][charToIndex('F')] = 1;
        arr[charToIndex('F')][charToIndex('J')] = 1;
        arr[charToIndex('M')][charToIndex('S')] = 1;
        arr[charToIndex('M')][charToIndex('Q')] = 1;
        arr[charToIndex('M')][charToIndex('N')] = 2;
        arr[charToIndex('M')][charToIndex('L')] = 1;
        arr[charToIndex('L')][charToIndex('R')] = 1;
        arr[charToIndex('L')][charToIndex('K')] = 3;
        arr[charToIndex('K')][charToIndex('P')] = 2;
        arr[charToIndex('K')][charToIndex('N')] = 1;
        arr[charToIndex('J')][charToIndex('S')] = 2;
        arr[charToIndex('S')][charToIndex('R')] = 1;
        arr[charToIndex('Q')][charToIndex('O')] = 1;
        arr[charToIndex('O')][charToIndex('R')] = 3;
        arr[charToIndex('O')][charToIndex('P')] = 1;
        arr[charToIndex('N')][charToIndex('P')] = 1;
    }

    /**
     * 数列与黄金分割
     * 根据题意所述“f[i]/f[i+1]会趋向于黄金分割”，因此当相邻两次计算相同时，计算结束
     * 保留小数方式：
     * 1.String.format("%.8f",f) 保留小数点后8位，不足不补零
     * 2.new DecimalFormat("0.00000000").format(f) 保留小数点后8位，不足补零；整数部分保留1位，不足补零
     *   new DecimalFormat("0.########").format(f) 保留小数点后8位，不足不补零
     */
    public static void t6(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double res = 1; //考虑n为1的情况
        long f1 = 1;
        long f2 = 1;
        long f3 = 0;
        for (int i = 3; i <= n + 1; i++) {
            f3 = f1 + f2;
            double cur = Double.parseDouble(String.format("%.8f",f2 * 1.0 / f3));
            if (res == cur){
                //System.out.println("i: " + i);
                break;
            }
            res = cur;
            //System.out.println(cur);
            f1 = f2;
            f2 = f3;
        }
        System.out.println(new DecimalFormat("0.00000000").format(res));
    }

    /**
     * 扫地机器人
     * 二分方法，二分每个机器人打扫的方格数量
     */
    public static void t7(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        //初始化l=1，一个小机器人最少扫一个，r=n，如果只有一个小机器人，那么它要扫全部
        int l = 1;
        int r = n;
        while (l < r){
            int mid = (l + r) >> 1;
            if (check(arr, mid, n)) r = mid;
            else l = mid + 1;
        }
        int res = (l - 1) * 2;
        System.out.println(res);
    }

    /**
     * 一个机器人在上一个机器人打扫的基础上，再扫 m 个方格，看是否能够打扫完
     * @param arr
     * @param m： 每个机器人打扫m格
     * @return
     */
    public static boolean check(int[] arr, int m, int n){
        int r = 0; //上个机器人所能够打扫到的有边界（包含）
        for (int i = 0; i < arr.length; i++) {
            //如果两个相邻机器人打扫的方格能够挨着
            //当Math.min(arr[i], r + 1)取arr[i]时 --- 上个机器人打扫区域在这个机器人的位置左边，为什么从arr[i]开始：因为arr[i]也要被打扫
            //                         取r + 1 时 ---上个机器人打扫区域覆盖了这个机器人的位置
            if (arr[i] - m <= r) r = Math.min(arr[i], r + 1) + m - 1;
        }
        return r >= n;
    }

    /**
     * 修改数组
     * 如果fa[num] = num代表num这个数还没有出现过
     * 如果fa[num] != num代表num所在分区的父节点fa[num]还没有被使用，如果有数字num'落在该分区，可以给其
     * 赋值fa[num]，然后区间右移动，即union(arr[i],arr[i] + 1)，保证区间最右边的数字（父节点）没有被使用过
     */
    public static void t8(){
        Scanner in = new Scanner(System.in);
        int N = 1000001; //要足够大，至少(1<=Ai<=1000000)
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int[] fa = new int[N];
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }
        for (int i = 0; i < n; i++) {
            if (arr[i] != findFa(fa, arr[i])){
                arr[i] = findFa(fa, arr[i]);
            }
            union(fa, arr[i], arr[i] + 1);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb.toString());
    }
    //需要路径压缩，否则会超时
    public static int findFa(int[] fa, int x){
        if (x == fa[x]){
            return x;
        }else{
            fa[x] = findFa(fa, fa[x]);
            return fa[x];
        }
    }
    public static void union(int[] fa, int a, int b){
        int f_a = findFa(fa, a);
        int f_b = findFa(fa, b);
        fa[f_a] = f_b;
    }
}
